import Node from '../types/INode'

import {btPrint} from 'hy-algokit'

 export class TreeNode<T> extends Node<T> {
    left : TreeNode<T> | null = null;
    right : TreeNode<T> | null = null;

    parent : TreeNode<T> | null = null;
    // 加get的时候  用这个isLeft的时候不用加括号
    get isLeft():boolean{
        // 当前节点父节点的左子节点等于自身，则当前节点的就是其的左子节点
        return !!(this.parent && this.parent.left ===this)
    }

    get isRight():boolean{
        // 当前节点父节点的左子节点等于自身，则当前节点的就是其的左子节点
        return !!(this.parent && this.parent.right ===this)
    }
}

    export class BSTree<T> {
        protected root: TreeNode<T> | null = null;

        private searchNode(value: T): TreeNode<T> | null {
            let current = this.root;
            let parent: TreeNode<T> | null = null;
            while(current){
                // 1、如果找到current 直接返回即可
                if (current.value === value) return current

                // 2、继续向下找
                parent = current;
                if (current.value < value) {
                    current = current.right
                } else {
                current = current.left
            }
            // 如果current有值，那么current保存自己的父节点
            if (current) current.parent = parent
            }
            return null;
        }

        // 这里用这种方法的原因是如果new的是AVL树的话他插入的节点不具有左旋和右旋的方法
        // 后面在AVL树里面对此方法进行重写，则插入的节点就会有AVL树对应的方法了
        protected createNode(value: T): TreeNode<T>{
            return new TreeNode(value)
        }

        protected checkBalance(node:TreeNode<T>,isAdd?:Boolean){}
        print(){
            btPrint(this.root)
        }

        // 插入数据的操作
        insert(value:T){
            // 1、根据传入value创建Node(TreeNode)节点
            const newNode = this.createNode(value)


            // 2、判断当前是否有根节点
            if(!this.root){//当前树为空
                this.root = newNode;
            }else{// 树中已经有其他值
                this.insertNode(this.root,newNode)
            }
            // 3、检查是否平衡
            this.checkBalance(newNode,true)
        }
        private insertNode(node: TreeNode<T>,newNode: TreeNode<T>){
            if(newNode.value < node.value){// 去左边继续查找空白位置
                if(node.left === null){// node节点的左边已经是空白
                    node.left = newNode
                    newNode.parent = node;
                }else{
                    this.insertNode(node.left,newNode)
                }
            }else{
                if(node.right === null){
                    node.right = newNode
                    newNode.parent = node;
                }else{
                    this.insertNode(node.right,newNode)
                }
            }
        }

        // 遍历的操作
        // 先序遍历
        preOrderTraverse(){
            this.preOrderTraverseNode(this.root)
        }
    private preOrderTraverseNode(node:TreeNode<T> | null){
            if(node){
                console.log(node.value)
                this.preOrderTraverseNode(node.left)
                this.preOrderTraverseNode(node.right)
            }
        }

        // 中序遍历
        inOrderTraverse(){
            this.inOrderTraverseNode(this.root)
        }
        private inOrderTraverseNode(node:TreeNode<T> | null){
            if(node){
                this.inOrderTraverseNode(node.left)
                console.log(node.value)
                this.inOrderTraverseNode(node.right)
            }
        }

        // 后序遍历
        postOrderTraverse(){
            this.postOrderTraverseNode(this.root)
        }
    private postOrderTraverseNode(node:TreeNode<T> | null){
            if(node){
                this.postOrderTraverseNode(node.left)
                this.postOrderTraverseNode(node.right)
                console.log(node.value)
            }
        }

        // 层序遍历(使用队列)
        levelOrderTraverse(){
            // 1、如果没有根节点，不需要遍历
            if(!this.root) return;
            // 2、创建队列
            const queue: TreeNode<T>[] = [];
            // 第一个节点是根节点
            queue.push(this.root);
            while(queue.length){
                // 3.1访问节点的过程,这里肯定是有数据的,素偶哦加个断言
                const current = queue.shift()!
                console.log(current.value)

                // 3.2 将左子节点放入到队列里面
                if(current.left){
                    queue.push(current.left);
                }
                // 3.2 将右子节点放入到队列里面
                if(current.right){
                    queue.push(current.right);
                }
            }
        }

        // 获取最值操作(最大值和最小值)
        getMaxValue(): T | null {
            let current = this.root;
            while(current && current.right){
                current = current.right;
            }
            return current?.value ?? null;
        }

        getMinValue(): T | null {
            let current = this.root;
            while(current && current.left){
                current = current.left;
            }
            return current?.value ?? null;
        }

        // 实现删除操作(在要删除的节点中的右子树中找出后继节点)
        private getSuccessor(delNode:TreeNode<T>): TreeNode<T>{
            // 获取右子树
            let current = delNode.right;
            let successor: TreeNode<T> | null = null;
            while(current){
                successor = current;
                current = current.left;
                if(current){
                    // 这里是让 successor一直有值,这样第172行的successor的父节点一定有值
                    current.parent = successor;
                }
            }

            // 拿到了后继节点,当后继节点不是要删除节点的右子节点时，要将要删除节点的右子节点整体的放在后继节点的右侧
            if(delNode.right != successor){
                // 后继节点不是叶子节点，但是后继节点要被提上去了，所以它的右节点(这里不会是左节点(不然后继节点将会是其的左节点))要被放在其父节点的子左侧
                successor!.parent!.left = successor!.right ?? null
                if(successor?.right){
                    successor.right.parent = successor.parent
                }
                // successor!.right =  delNode.right;
            }else {
                delNode.right = successor!.right
                if(successor!.right){
                    successor!.right.parent = delNode
                }
            }



            // 找到后继节点
            console.log('删除节点',delNode.value,'后继节点',successor?.value)

            // 一定要进行的操作,将删除节点的left ,赋值给后继节点的left
            // successor!.left = delNode.left
            return successor!
        }

        // 搜索特定的值：20 => boolean
        search(value:T):boolean {
            return !!this.searchNode(value)
        }

        remove(value:T):boolean {
            // 1、搜索当前是否有value
            let current = this.searchNode(value)
            if(!current) return false

            let delNode: TreeNode<T> = current;
            let replaceNode: TreeNode<T> | null = null

            // 2、获取到3个东西: 当前节点/父节点/是属于父节点的左子节点还是右子节点
            // console.log('当前节点',current?.value,"父节点:",current?.parent?.value)
            // 2、如果删除的是叶子节点
            if(current.left === null && current.right === null){ //删除的是根节点
                replaceNode = null;
            }else if(current.right === null){ // 删除的只有左子节点
                replaceNode = current.left;
            }else if(current.left === null){ // 删除的只有右子节点
                replaceNode = current.right;
            }else{ // 删除的节点有两个节点(要找到其的后继节点)
                const successor = this.getSuccessor(current)
                // 这里通过直接将要删除掉的节点的value换成后继节点的value，完成操作(这里还要对后继节点的子节点进行处理)
                current.value = successor.value;
                delNode = successor;
                this.checkBalance(delNode,false)
                return true;
                // replaceNode = current
            }

            // 给要替换后的节点设置父节点
            if(current === this.root){
                this.root = replaceNode;
            }else if(current.isLeft){
                current.parent!.left = replaceNode
            }else{
                current.parent!.right = replaceNode
            }

            // 判断replaceNode,这里保证每一届节点在进行删除操作后依然有其对应的父节点，
            if(replaceNode && current.parent){
                replaceNode.parent = current.parent
            }

            // 删除完成后，检查树是否平衡(传入的节点是那个真正从二叉树中移除的节点)，所以这里要找到被移除的节点
            this.checkBalance(delNode,false)
            return true
        }
    }

 const bst = new BSTree<number>()

export default {}